package lc;

import java.util.ArrayList;
import java.util.HashMap;

public class ParlindromPartitioning {
	HashMap<String, ArrayList<ArrayList<String>>> cache = new HashMap<>();
	public ArrayList<ArrayList<String>> partition(String s) {
		ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
		if (s == null || s.length() == 0) {
			ArrayList<String> list = new ArrayList<String>();
			result.add(list);
			return result;
		} else if (s.length() == 1) {
			ArrayList<String> list = new ArrayList<String>();
			list.add(s);
			result.add(list);
			return result;
		}
		
		for (int i = 1; i <= s.length(); i++) {
			String head = s.substring(0, i);
			if (!isParlindrom(head)) {
				continue;
			}
			
			String tail = s.substring(i, s.length());
			ArrayList<ArrayList<String>> sublists;
			if (cache.containsKey(tail)) {
				sublists=cloneLists(cache.get(tail));
			}
			else {
				sublists = partition(tail);
				cache.put(tail, cloneLists(sublists));
			}
			for (ArrayList<String> sublist : sublists) {
				sublist.add(0, head);
				result.add(sublist);
			}
		}
		return result;
	}

	static ArrayList<ArrayList<String>> cloneLists(ArrayList<ArrayList<String>> sublists) {
		ArrayList<ArrayList<String>> result = new ArrayList<ArrayList<String>>();
		for (ArrayList<String> list : sublists) {
			result.add((ArrayList<String>) list.clone());
		}
		return result;
	}
	
	static boolean isParlindrom(String s) {
		char[] word = s.toCharArray();
		int i1 = 0;
		int i2 = word.length - 1;
		while (i2 > i1) {
			if (word[i1] != word[i2]) {
				return false;
			}
			i1++;
			i2--;
		}
		return true;
	}

	public static void main(String ...strings) {
		ParlindromPartitioning sol = new ParlindromPartitioning();
		ArrayList<ArrayList<String>> partition = sol.partition("cbbc");
		System.out.println(partition);
		
		partition = sol.partition("bb");
		System.out.println(partition);
	}
	
}
